#include <bits/stdc++.h>
using namespace std;

// class Solution {
// public:
//     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
//     {
//         if(gas.empty() || cost.empty())
//         {
//             return -1;
//         }

//         for(int start = 0; start < gas.size(); ++start)
//         {
//             int sum = 0;

//             for(int i = start; i < gas.size(); ++i)
//             {
                
//                 int cur = (start + i) % gas.size();
//                 sum += gas[cur] - cost[cur];

//                 if(sum < 0)
//                 {
//                     break;
//                 }
//             }

//             if(sum >= 0)
//             {
//                 return start;
//             }
//         }
        
        
//         return -1;
//     }
// };

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
    {
        if(gas.empty() || cost.empty())
        {
            return -1;
        }

        int total = 0;
        int current = 0;
        int start = 0;

        for(int i = 0; i < gas.size(); ++i)
        {
            total += gas[i] - cost[i];
            current += gas[i] - cost[i];

            if(current < 0)
            {
                start = i+1;
                current = 0;
            }
        }

        return total >= 0 ? start : -1;
    }
};




#include <stdio.h>
#include <stdlib.h>

struct hashNode {
    int data;
    int index;
    struct hashNode* next;
};

void put(int value, int idx, int size, struct hashNode* hashTable[]) {
    int hash = abs(value) % size;  // 使用绝对值确保哈希值为正
    struct hashNode* newNode = (struct hashNode*)malloc(sizeof(struct hashNode));
    newNode->data = value;
    newNode->index = idx;
    newNode->next = hashTable[hash];
    hashTable[hash] = newNode;  // 头插法
}

int find(int target, int currentValue, int size, struct hashNode* hashTable[]) {
    int complement = target - currentValue;
    int hash = abs(complement) % size;
    struct hashNode* current = hashTable[hash];
    
    while (current != NULL) {
        if (current->data == complement) {
            return current->index;
        }
        current = current->next;
    }
    return -1;
}

int main() {
    const int SIZE = 4;
    struct hashNode* hashTable[SIZE] = { NULL };  // 初始化为NULL
    int arr[SIZE];
    int targetSum;

    printf("请输入十个整数:\n");
    for (int i = 0; i < SIZE; i++) {
        scanf("%d", &arr[i]);
    }

    printf("请输入你要查找的和的值:\n");
    scanf("%d", &targetSum);

    for (int i = 0; i < SIZE; i++) {
        int complementIndex = find(targetSum, arr[i], SIZE, hashTable);
        if (complementIndex != -1 && complementIndex != i) {  // 避免同一个元素使用两次
            printf("找到匹配对: [%d, %d]\n", complementIndex, i);
            // 释放内存
            for (int j = 0; j < SIZE; j++) {
                struct hashNode* current = hashTable[j];
                while (current != NULL) {
                    struct hashNode* temp = current;
                    current = current->next;
                    free(temp);
                }
            }
            return 0;
        }
        put(arr[i], i, SIZE, hashTable);
    }

    printf("未找到和为%d的匹配对\n", targetSum);
    
    // 释放内存
    for (int j = 0; j < SIZE; j++) {
        struct hashNode* current = hashTable[j];
        while (current != NULL) {
            struct hashNode* temp = current;
            current = current->next;
            free(temp);
        }
    }

    return 0;
}